package main

type Node struct {
	Val   int
	Prev  *Node
	Next  *Node
	Child *Node
}

func dfs(node *Node) *Node {
	tail := node
	for node != nil {
		if node.Next == nil {
			tail = node
		}

		if node.Child != nil {
			t := dfs(node.Child)
			tail = t
			next := node.Next
			node.Next = node.Child
			node.Child.Prev = node
			node.Child = nil
			t.Next = next
			if next != nil {

				next.Prev = t
			}
			node = t
		}
		node = node.Next
	}

	return tail
}

func flatten(root *Node) *Node {

	dfs(root)

	return root

}
